#define _CRT_SECURE_NO_WARNINGS 1




class Partition {
public:
    ListNode* partition(ListNode* phead, int x)
    {
        if (phead == NULL || phead->next == NULL)
            return phead;

        ListNode* cur = phead;
        ListNode* smallhead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* smalltail = smallhead;
        ListNode* bighead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* bigtail = bighead;

        while (cur != NULL)
        {
            if (cur->val < x)
            {
                smalltail->next = cur;
                smalltail = cur;
                cur = cur->next;
            }
            else
            {
                bigtail->next = cur;
                bigtail = cur;
                cur = cur->next;
            }
        }

        if (smallhead == smalltail)
        {
            return bighead->next;
        }
        if (bighead == bigtail)
        {
            return smallhead->next;
        }

        smalltail->next = bighead->next;
        bigtail->next = NULL;
        return smallhead->next;
    }
};
